Forecasting the cost of processing multi-join queries via hashing for main-memory databases (Extended version)

摘要

Database management systems (DBMSs) carefully optimize complex multi-joinqueries to avoid expensive disk I/O. As servers today feature tens or hundredsof gigabytes of RAM, a significant fraction of many analytic databases becomesmemory-resident. Even after careful tuning for an in-memory environment, alinear disk I/O model such as the one implemented in PostgreSQL may make queryresponse time predictions that are up to 2X slower than the optimal multi-joinquery plan over memory-resident data. This paper introduces a memory I/O costmodel to identify good evaluation strategies for complex query plans withmultiple hash-based equi-joins over memory-resident data. The proposed costmodel is carefully validated for accuracy using three different systems,including an Amazon EC2 instance, to control for hardware-specific differences.Prior work in parallel query evaluation has advocated right-deep and bushytrees for multi-join queries due to their greater parallelization andpipelining potential. A surprising finding is that the conventional wisdom fromshared-nothing disk-based systems does not directly apply to the modernshared-everything memory hierarchy. As corroborated by our model, theperformance gap between the optimal left-deep and right-deep query plan cangrow to about 10X as the number of joins in the query increases.